A virtual private network (VPN) securely connects multiple customer sites that are possibly geographically dispersed and wish to communicate among each other. A virtual private network is essentially a secure, private communication network that utilizes a service provider's network (such as AT&T's core network) in order to connect remote sites and users together. In many cases, virtual private network customers contract with the virtual private network service provider to have the service provider manage their virtual private network assets.
In order to maintain reachability and network availability service level agreements, a service provider often monitors the reachability among endpoints in a customer's virtual private network across that service provider's network. A service provider will attempt to detect with high probability a situation in which traffic cannot be sent from a virtual private network interface on one provider edge router to a virtual private network interface on another provider edge router within the same virtual private network. In other words, a service provider monitors site-to-site reachability between customer sites in customer virtual networks.
In one conventional method of reachability testing, the reachability must be tested between every pair-wise combination of provider-edge/customer-edge links (interfaces) within the context of each customer virtual private network. It is obvious that such conventional methods do not scale well in large networks. The number of reachability tests that must be conducted is a factor of both the number the customer virtual private networks, as well as the number of pairs of interfaces within each of those customer virtual private networks. Furthermore, since a single provider edge router often supports numerous virtual private networks, reachability tests are repeated numerous times on those provider edge routers.
As a network grows, the number of reachability tests required while using conventional methods grows exponentially. Such a large increase in the number of reachability tests invariably increases the time required in order to perform reachability testing. This is especially true when a full network reachability test is performed for all customer virtual private networks supported by the service provider's network. Furthermore, as the number of reachability tests increases, the amount of test traffic on the network increases, using valuable network resources that can no longer be used to support customer traffic and services.
In addition to exhaustively testing pair-wise reachability between every pair of interfaces within the context of each customer virtual private network, another method of testing customer virtual private network interfaces involves building, in an offline network management system, a model of the label switched paths that constitute the network. The network management system then queries the network for status on each of the label switched paths, and constructs a cause-effect relationship within the offline management system that relates a label switched path failure to that of a pair of virtual private network interfaces.
Unfortunately, this method of modeling label switched paths in an offline network management system has a number of disadvantages. There is no simple, scalable method of querying the status of every label switched path within the network. Furthermore, since single-hop label switched paths may be shared among multiple customer virtual private networks, and this mapping is done dynamically, it is difficult to attribute the failure of a label switched path to the set of customer virtual private networks that are affected.
As such, a need exists in the art for a simple, scalable method of testing site-to-site reachability within the context of customer virtual private networks by testing connectivity between pairs of provider edge routers in a service provider network, and verifying existence of routes associated with edge communication links (links from a customer edge router to a provider edge router) to ensure the links are operational.